/*
 * @lc app=leetcode.cn id=1646 lang=cpp
 *
 * [1646] 获取生成数组中的最大值
 */

// @lc code=start
class Solution
{
public:
  int getMaximumGenerated(int n)
  {
    if (n < 2)
      return n;
    vector<int> v(n + 1);
    v[0] = 0;
    v[1] = 1;
    int ans = 1;
    for (int i = 2; i <= n; ++i) {
      int k = i / 2;
      if (i % 2)
        v[i] = v[k] + v[k + 1];
      else
        v[i] = v[k];
      ans = max(ans, v[i]);
    }
    return ans;
  }
};
// @lc code=end
